package dynamic.division;

import tree.TreeNode;

/**
 * @Classname : HouseRobberIII
 * @Description : 337. 打家劫舍 III
 * https://leetcode.cn/problems/house-robber-iii/
 * @Author : cty
 * @Date 2023/4/6 22:04
 */


public class HouseRobberIII {
    // 二叉树后序遍历+动态规划
    public int rob(TreeNode root) {
        // c-当前节点、l-左子节点、r-右子节点
        // c[0] 选择当前节点的最大权值和 f(c) = c.val + g(l) + g(r)
        // c[1] 不选择当前节点的最大权值和 g(c) = Math.max(f(l), g(l)) + Math.max(f(r), g(r))
        int[] c = dfs(root);
        return Math.max(c[0], c[1]);
    }

    private int[] dfs(TreeNode node) {
        if (node == null) return new int[]{0, 0};

        int[] l = dfs(node.left);
        int[] r = dfs(node.right);
        int select = node.val + l[1] + r[1];
        int noSelect = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
        return new int[]{select, noSelect};
    }
}
